﻿#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
	void InOrderConvert(Node* cur, Node*& prev)
	{
		if (cur == nullptr)
			return;
		// 中序遍历
		InOrderConvert(cur->left, prev);
		// 当前结点的左，指向前⼀个结点
		cur->left = prev;
		// 前⼀个结点的右，指向当前结点
		if (prev)
			prev->right = cur;
		prev = cur;
		InOrderConvert(cur->right, prev);
	}
	Node* treeToDoublyList(Node* root) {
		if (root == nullptr)
			return nullptr;
		Node* prev = nullptr;
		InOrderConvert(root, prev);
		// 从根开始往左⾛，找到第⼀个结点
		Node* head = root;
		while (head->left)
		{
			head = head->left;
		}
		// head为第⼀个结点，prev是最后⼀个结点
		// 题⽬要求为循环链表，进⾏⼀些链接
		head->left = prev;
		prev->right = head;
		return head;
	}
};